The need for designing minimum-cost networks that will provide redundant coverage arises in several contexts. In telecommunications, for example, in designing cellular telephone networks it is necessary to decide where to position cellular antennas so that each customer has coverage. In order to maintain coverage in the event a particular antenna fails, it is desirable to design networks so that each customer is provided with coverage from multiple antennas. Each potential location for positioning an antenna has both an associated customer coverage and an associated cost, and it is desirable to select from potential locations those that will provide the least-cost network that will provide the desired multiple coverage.
Another example of the need for minimum-cost redundant coverage arises in the design of modem locations for telephone access by ISP users. It is highly desirable to position modems near customers so that their access costs are minimized and to provide multiple coverage so that service can continue in the event a modem fails. A least-cost network that will provide the desired multiple coverage is advantageous.
Another example of the need for minimum-cost redundant coverage arises in the placement of DSL hubs for access by subscribers. It is necessary to position the hubs within transmission range of customers and also desirable to provide multiple coverage so that service can continue in the event of failure. A least-cost network that will provide multiple coverage is advantageous.
Still another example arises in the context of computational biology, in the minimum robust tagging SNP problem. A single nucleotide polymorphism (SNP) occurs when a specific position in the DNA sequence of a population most commonly assumes two alternative values from the set {A,C,T,G} while its neighbors are unaltered. A set of SNPs in a region of DNA that tends to be inherited together is called a haplotype. The strong association between SNPs in a haplotype implies that a small subset of these SNPs, called tag SNPs, can provide enough information about the remaining SNPs in that region. Using tag SNPs for association studies can significantly reduce the cost of genotyping, since not all SNPs will have to be genotyped. Given a group of p haplotypes with n SNPs each, the minimum tagging SNP problem (MTS) consists in finding the smallest subgroup of SNPs that is able to distinguish each haplotype from the others in the group. However, it may occur that some tag SNPs are missing in one or more haplotypes. In this case, there exists a subgroup of SNPs, named robust tag SNPs, which is able to distinguish each pair of haplotypes unambiguously when at most a given number of SNPs is missing. The MTS problem thus presents the same need to find a minimum collection or network of elements that “cover” a set of objects.
Design problems of the type described above can be generalized as follows: In the K-set covering problem, we are given N sets and M objects. Each set covers one or more objects and has a cost associated with its deployment. We wish to determine the least-cost subset of sets such that each object is covered by at least K sets. Suppose we are given N potential locations where a PoP (or point of presence) can be deployed. The cost of deploying a PoP at location L is C(L). Furthermore, suppose we are given a set of M customers that require some type of service that is provided by systems in the PoP. Each potential PoP location can cover, or provide the service, to a subset of customers (usually customers that are closely located to the PoP). For a customer to be able to get service there must be at least one deployed PoP that can cover the customer. To avoid loss of service in the event of failure, we would like each customer to be covered by at least K PoPs (for example, K=2 gives minimum protection). Thus, we would like to be able to determine the least-cost subset of PoP locations such that each customer is covered by at least K PoPs.
An extremely simple example of this design problem is illustrated in FIG. 1A, which shows a set of six potential PoP locations L1 through L6 with respective costs C1 through C6, and a set of four customers Ma through Md which are serviced, or covered, by the locations as follows: customer Ma is covered by L1, L3 and L5; customer Mb by L1, L2 and L3; customer Mc by L2, L3 and L4; and customer Md by L4 and L6. The dashed lines from each customer M to a location L indicate which locations can cover that customer. In this example, costs C1, C3, C5 and C6 are 1 unit, costs C2 and C6 are 2 units, and we would like dual coverage so we select K=2. We would like to determine the least-cost subset of PoP locations L1 through L6 such that each customer is covered by at least 2 PoPs.
FIG. 1B shows a least cost solution to the coverage design problem illustrated in FIG. 1A. As shown, locations L1, L3, L4 and L6 provide 2-fold coverage to each of the customers Ma through Md with a total cost of 4 units.
One statement of the set covering problem is as follows:
Given n finite sets P1, P2, . . . , Pn, let cj be the cost associated with set Pj, for j=1, . . . , n. Denote sets
  I  =                              ⋃                      j            =            1                          n            ⁢              P        j              =          {              1        ,        …        ⁢                                  ,        m            }      
and J={1, . . . , n}. An element of set I is called an object. A subset Ĵ of J is called a cover if
            ⋃              j        ∈                  J          ^                      ⁢          P      j        =      I    .  
The cost of cover Ĵ is ΣjεĴcj. The set covering problem is to find a cover J* of minimum cost. The set multi-covering problem is a generalization of the set covering problem where each object i ε I must be covered by at least li sets. A special case of the set multi-covering problem arises when li=k for all i ε I, which is called the k-set covering problem.
It would be advantageous to be able to find solutions to the general k-set covering problem stated above to enable minimum-cost networks to be designed from potential network elements having defined costs and coverages. For small scale examples, where the number of network elements n is not great, it is possible to use brute force techniques that compare costs of all possible combinations of elements that provide the desired cover. For larger scale examples, where an optimal solution would require prohibitive amounts of computer capacity or computation time, approximation methods are necessary.
Attempts using heuristics and algorithms in approximation methods to find solutions to variants of the set covering problem appear in the prior art.
For example, a branch-and-bound algorithm to solve small instances of multicover is described by Gonsalvez et al. (D. J. GONSALVEZ, N. G. HALL, W. T. RHEE, and S. P. SIFERD, Heuristic Solutions And Confidence Intervals For The Multicovering Problem, European Journal of Operational Research, 31(1):94-101, 1987).
In the computational biology field, the MSP problem was formulated as a k-set cover problem and shown to be NP-hard by Huang et al. (Y. HUANG, K. ZHANG, T. CHEN, and K. M. CHAO Selecting Additional Tag SNPs for Tolerating Missing Data in Genotyping, BMC Bioinformatics, 6:263-278, 2005). To find robust tag SNPs, Huang et al. proposed two greedy algorithms and a linear programming relaxation. Chang et al. developed a hybrid method that combines the ideas of the branch-and-bound method and the greedy algorithm of Huang et al. (C. J. CHANG, Y. HUANG, and K. M. CHAO, A Greedier Approach For Finding Tag SNPs, Bioinformatics, 22(6):685-691, 2006). Pessôa and Ribeiro proposed an algorithm based on the GRASP metaheuristic (L. S. PESSÔA and C. C. RIBEIRO, A GRASP For The Minimum Informative Subset Problem, In CIRRELT, editor, Proceedings of the Seventh Metaheuristics Inter-national Conference (MIC2007), pages 44-44, 2007).
GRASP is short for greedy randomized adaptive search procedure. It was introduced for a set covering problem with unit costs. (T. A. FEO and M. G. C. RESENDE, A probabilistic heuristic for a computationally difficult set covering problem, Operations Research Letters, vol. 8, pp. 67-71, 1989). GRASP is a multi-start metaheuristic which consists in applying local search from feasible starting solutions generated by a randomized greedy heuristic. GRASP iterations are independent, i.e. a solution generated in one iteration is not influenced by solutions found in previous iterations.
Path-relinking is a known intensification scheme that explores paths in the solution space connecting good-quality solutions (F. GLOVER, Tabu Search and Adaptive Memory Programming—Advances, Applications and Challenges, In R. S. Barr, R. V. Helgason, and J. L. Kennington, editors, INTERFACES IN COMPUTER SCIENCE AND OPERATIONS RESEARCH, pages 1-75. Kluwer, 1996). Laguna and Marti introduced a scheme for integrating path-relinking within a GRASP (M. LAGUNA and R. MARTÍ, GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization, INFORMS Journal on Computing, 11:44-52, 1999). Since its introduction much research has been done to enhance GRASP with path-relinking (M. G. C. RESENDE and C. C. RIBEIRO, GRASP with Path-Relinking: Recent Advances and Applications, In T. Ibaraki, K. Nonobe, and M. Yagiura, editors, METAHEURISTICS: PROGRESS AS REAL PROBLEM SOLVERS, pages 29-63. Springer, 2005).
Another approach which has been tried to find approximate solutions for variants of the set covering problem uses a Lagrangian relaxation heuristic (J. E. BEASLEY, A Lagrangian Heuristic for Set-Covering Problems, Naval Research Logistics, 37(1):151-164, 1990; J. E. BEASLEY, An Algorithm for Set-Covering Problem, European Journal of Operational Research, 31:85-93, 1987; J. E. BEASLEY, Lagrangean Relaxation, in C. R. Reeves, editor, MODERN HEURISTIC TECHNIQUES FOR COMBINATORIAL PROBLEMS, pages 243-303, Blackwell Scientific Publications, Oxford, U.K. and Boston Mass., 1993). Efforts to improve upon Beasley's Lagrangian relaxation heuristic have been presented. (K. TECHAPICHETVANICH and D. BRICKER, Investigation of Lagrangian Heuristics for Set Covering Problems, Department of Industrial Engineering, The University of Iowa, 1993, a copy of which is available at http://citeseer.ist.psu.edu/cache/papers/cs/25439/http:zSzzSzasrl.ecn.uiowa.eduzS zdbrickerzSzPaperszSzSCP_heuristics.pdf/techapichetvanich93investigation.pdf)
None of these prior art techniques provide minimum-cost network design methods for networks with large numbers of network elements that model the design as a k-set covering problem and are able to provide sufficiently accurate approximate solutions to the k-set covering problem in reasonable times, using reasonable amounts of computer resources.
Accordingly, it would be desirable to find methods, computer program products and computer systems using algorithms or heuristics that are operable on standard computer architectures and that are able to find good approximate solutions to network design problems where real world network element costs and coverages can be modeled as k-set cover problems in large scale instances and solutions achieved in reasonable times, using reasonable amounts of computer resources. More particularly, there is a need to provide a method and system for designing a telecommunications network by selecting the least-cost set of PoPs from a possible collection of PoPs each having an assigned cost and coverage and that will provide a desired k-coverage to customers/objects serviced by the PoPs. Networks designed by such methods have the advantage of minimal or near-minimal cost, and give their operators a cost savings that provides a competitive advantage. Having customers covered by at least k PoPs improves system availability for the customers and thus overall customer satisfaction.